package object;

import java.util.Arrays;
import java.util.Stack;


public class Sort {
    public static void insertSort(int[] arr) {
        if (arr == null) {
            return;
        }
        //默认区间是前闭后开，有序元素区间[0,bound),无序区间[bound，arr.length)
        //每次拿无需元素的区间的第一个元素，拿有序区间从最后一个元素从后往前遍历比较
        //以升序为例
        for ( int bound = 1; bound < arr.length; bound++) {
            int value = arr[bound];
            int cur = bound - 1;
            for (; cur >=0; cur--) {
                if (arr[cur] > value) {
                    //向后迁移移元素
                    arr[cur + 1] = arr[cur];
                } else {
                    break;
                }
            }
            arr[cur + 1] = value;
        }
    }
    //希尔排序,以升序为例
    //其实希尔排序就是直接插入排序的改良版，多进行了几次直接插入
    public static void shellSort(int[] arr) {
        if (arr == null) {
            return;
        }
        //采取长度除以2的方式更高效
        int gap = arr.length / 2;
        while (gap >= 1) {
            System.out.println("gap" + " = " + gap +": "+ Arrays.toString(arr));
            shellSortHelper(arr,gap);
            gap /= 2;
        }
    }

    private static void shellSortHelper(int[] arr, int gap) {
        if (arr == null) {
            return;
        }
        for ( int bound = gap; bound < arr.length; bound++) {
            int value = arr[bound];
            int cur = bound - gap;
            for (; cur >=0; cur -= gap) {
                if (arr[cur] < value) {
                    arr[cur + gap] = arr[cur];
                } else {
                    break;
                }
            }
            arr[cur + gap] = value;
        }
    }
    //直接选择排序
    public static void selectSort(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int bound = 0; bound < arr.length - 1; bound++) {
            for (int cur = bound + 1; cur < arr.length; cur++) {
                if (arr[cur] < arr[bound]) {
                    int tmp = arr[bound];
                    arr[bound] = arr[cur];
                    arr[cur] = tmp;
                }
            }
        }
    }
    //堆排序(升序)
    public static void heapSort(int[] arr) {
        if (arr == null) {
            return;
        }
        createHeap(arr);
        int bound = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {
            int tmp = arr[0];
            arr[0] = arr[bound];
            arr[bound] = tmp;
            shiftDown(arr,bound,0);
            bound--;
        }


    }
    public static void createHeap(int[] arr) {
        if (arr == null) {
            return;
        }
        int lastNotLeaf = (arr.length - 1 - 1) / 2;
        for (int i = lastNotLeaf; i >= 0; i--) {
            shiftDown(arr,arr.length,i);
        }
    }

    private static void shiftDown(int[] arr,int length ,int index) {
        if (arr == null) {
            return;
        }
        int parent = index;
        int child = 2 * parent + 1;
        while (child < length) {
            if (child + 1 < length && arr[child + 1] > arr[child]) {
                child = child + 1;
            }
            if (arr[child] > arr[parent]) {
                int tmp = arr[child];
                arr[child] = arr[parent];
                arr[parent] = tmp;
            } else {
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }
    //冒泡排序
    //从前往后比较
    public static void bubbleSort(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j +1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
    //从后往前比较
    public static void bubbleSort1(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = arr.length - 1; j > i; j--) {
                if (arr[j - 1] > arr[j]) {
                    int tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }
    //快速排序
    public static void quickSort(int[] arr) {
        quickSort(arr,0,arr.length  - 1);
    }
    //辅助快速排序
    public static void quickSort(int[] arr,int left,int right) {
        if (left >= right) {
            return;
        }
        int index = partition(arr,left,right);
        quickSort(arr,left,index - 1);
        quickSort(arr,index + 1,right);
    }
    public static int partition(int[] arr,int left,int right) {
        mediaOfThree(arr,left,right);
        int value = arr[right];
        int l = left;
        int r = right;
        while (l < r) {
            while (l < r && arr[l] <= value) {
                l++;
            }
            while (l < r && arr[r] >= value) {
                r--;
            }
            swap(arr,l,r);
        }
        swap(arr,l,right);
        return l;
    }
    public static void swap(int[] arr,int l,int r) {
        int tmp = arr[l];
        arr[l] = arr[r];
        arr[r] = tmp;
    }
    //优化方案：三数排序法
    public static void mediaOfThree(int[] arr,int left,int right) {
        //当数组元素的个数小于等于2个时，不需要三数取中，直接返回
        if (right - left < 2) {
            return;
        }
        //下述代码,可以实现三数取中法
//        int mid = arr[(left + right) / 2];
//        int first = arr[left];
//        int last = arr[right];
//        if (first < mid) {
//             if (first > last) {
//                 swap(arr,left,right);
//             }
//        } else {
//            if (mid > last) {
//                swap(arr,(left + right) / 2,last);
//            }
//        }
        //三数取中法的优化方案
        int mid = left + (right - left) / 2;
        if (arr[left] > arr[mid]) {
            swap(arr,left,mid);
        }
        if (arr[left] > arr[right]) {
            swap(arr,left,right);
        }
        if (arr[mid] > arr[right]) {
            swap(arr,mid,right);
        }
        swap(arr,mid,right);
    }
    //快速排序非递归版
    static class Range {
        public int left;
        public int right;

        public Range(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }
    public static void quickSortByLoot(int[] arr) {
        Stack<Range> stack = new Stack<>();
        stack.push(new Range(0,arr.length - 1));
        while (!stack.isEmpty()) {
            Range range = stack.pop();
            if (range.left >= range.right) {
                continue;
            }
            int index = partition(arr,range.left,range.right);
            quickSort(arr,range.left,index - 1);
            quickSort(arr,index + 1,range.right);
        }
    }
    //归并排序
    public static void mergeSort(int[] arr) {
        mergeSort(arr,0,arr.length - 1);
    }

    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid + 1,right);
        merge(arr,left,mid,right);
    }
    //此时把长度为N的数组分为了N个长度为1的有序数组,接下来就要两两合并了
    //这两个区间分别是[left,mid],[mid + 1,right],合并之后长度为：right - left + 1
    public static void merge(int[] arr,int left,int mid,int right) {
        int[] result = new int[right - left + 1];
        int resultIndex = 0;
        //接下来有点像合并两个链表
        int cur1 = left;
        int cur2 = mid + 1;
        while (cur1 <= mid && cur2 <= right) {
            if (arr[cur1] <= arr[cur2]) {
                result[resultIndex++] = arr[cur1];
                cur1++;
            } else {
                result[resultIndex++] = arr[cur2];
                cur2++;
            }
        }
        //区间长度不一定一样,因为数组元素可能是奇数或偶数
        //把多余的元素放到数组中
        while (cur1 <= mid) {
            result[resultIndex++] = arr[cur1];
            cur1++;
        }
        while (cur2 <= right) {
            result[resultIndex++] = arr[cur2];
            cur2++;
        }
        //最后把自己创建的数组的元素转移到原数组中
        for (int i = 0; i < result.length; i++) {
            arr[left + i] = result[i];
        }
    }
    //归并排序非递归版
    public static void mergeSortByLoop(int[] arr) {
        for (int size = 1;size < arr.length; size *= 2) {
            for (int i = 0; i < arr.length; i += 2 * size) {
                int left = i;
                int mid = i + size - 1;
                if (mid >= arr.length - 1) {
                    mid = arr.length - 1;
                }
                int right = i + 2 * size - 1;
                if (right >= arr.length - 1) {
                    right = arr.length - 1;
                }
                merge(arr,left,mid,right);
            }
        }
    }




    public static void main(String[] args) {
        int[] arr = {4,2,8,10,0,6};
        int[] arr1 = {9,3};
        //insertSort(arr);
        //shellSort(arr);
        //selectSort(arr);
        //heapSort(arr);
        //bubbleSort1(arr);
        //quickSort(arr);
        //quickSortByLoot(arr);
        //mergeSort(arr);
        mergeSortByLoop(arr);
        System.out.println(Arrays.toString(arr));
    }

}
